home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / elm / elm2.4 / lib / ndbz.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-11  |  37.0 KB  |  1,439 lines
  1. static char rcsid[] = "@(#)$Id: ndbz.c,v 5.6 1993/02/08 00:18:11 syd Exp $";
  2.  
  3. /*******************************************************************************
  4.  *  The Elm Mail System  -  $Revision: 5.6 $   $State: Exp $
  5.  *
  6.  *            Copyright (c) 1988-1992 USENET Community Trust
  7.  *            Copyright (c) 1986,1987 Dave Taylor
  8.  *******************************************************************************
  9.  * Bug reports, patches, comments, suggestions should be sent to:
  10.  *
  11.  *    Syd Weinstein, Elm Coordinator
  12.  *    elm@DSI.COM            dsinc!elm
  13.  *
  14.  *******************************************************************************
  15.  * $Log: ndbz.c,v $
  16.  * Revision 5.6  1993/02/08  00:18:11  syd
  17.  * fix taghere to be || instead of | and paren to make
  18.  * it catch duplicates again, as per testing.
  19.  * From: Syd and Chip Rosenthal
  20.  *
  21.  * Revision 5.5  1993/02/03  15:26:13  syd
  22.  * protect atol in ifndef __STDC__ as some make it a macro, and its in stdlib.h
  23.  *
  24.  * Revision 5.4  1993/01/27  20:40:10  syd
  25.  * make code match cnews dbz, remove extra | taghere in search,
  26.  * that was causing a compiler error anyway, as improper code
  27.  * From: Syd, via prompt from Denis Lambot
  28.  *
  29.  * Revision 5.3  1992/12/12  01:29:26  syd
  30.  * Fix double inclusion of sys/types.h
  31.  * From: Tom Moore <tmoore@wnas.DaytonOH.NCR.COM>
  32.  *
  33.  * Revision 5.2  1992/10/11  01:46:35  syd
  34.  * change dbm name to dbz to avoid conflicts with partial call
  35.  * ins from shared librarys, and from mixing code with yp code.
  36.  * From: Syd via prompt from Jess Anderson
  37.  *
  38.  * Revision 5.1  1992/10/03  22:41:36  syd
  39.  * Initial checkin as of 2.4 Release at PL0
  40.  *
  41.  *
  42.  ******************************************************************************/
  43.  
  44. /** 
  45.     multi-database dbm replacement
  46.  
  47. **/
  48.  
  49. /*
  50.  
  51. ndbz.c  V1.0
  52. Syd Weinstein <syd@dsi.com>
  53. Based on dbz.c from the C News distribution
  54. Modified to support multiple DBZ files.
  55.  
  56. Copyright 1988 Jon Zeeff (zeeff@b-tech.ann-arbor.mi.us)
  57. You can use this code in any manner, as long as you leave my name on it
  58. and don't hold me responsible for any problems with it.
  59.  
  60. Hacked on by gdb@ninja.UUCP (David Butler); Sun Jun  5 00:27:08 CDT 1988
  61.  
  62. Various improvments + INCORE by moraes@ai.toronto.edu (Mark Moraes)
  63.  
  64. Major reworking by Henry Spencer as part of the C News project.
  65.  
  66. These routines replace dbm as used by the usenet news software
  67. (it's not a full dbm replacement by any means).  It's fast and
  68. simple.  It contains no AT&T code.
  69.  
  70. In general, dbz's files are 1/20 the size of dbm's.  Lookup performance
  71. is somewhat better, while file creation is spectacularly faster, especially
  72. if the incore facility is used.
  73.  
  74. */
  75.  
  76. #include "headers.h"
  77. #include <ctype.h>
  78. #include <errno.h>
  79. #ifndef ANSI_C
  80. extern int errno;
  81. #endif
  82.  
  83. /*
  84.  * #ifdef index.  "LIA" = "leave it alone unless you know what you're doing".
  85.  *
  86.  * FUNNYSEEKS    SEEK_SET is not 0, get it from <unistd.h>
  87.  * INDEX_SIZE    backward compatibility with old dbz; avoid using this
  88.  * NMEMORY    number of days of memory for use in sizing new table (LIA)
  89.  * INCORE    backward compatibility with old dbz; use dbzincore() instead
  90.  * DEFSIZE    default table size (not as critical as in old dbz)
  91.  * NOTAGS    fseek offsets are strange, do not do tagging (see below)
  92.  * NPAGBUF    size of .pag buffer, in longs (LIA)
  93.  * SHISTBUF    size of ASCII-file buffer, in bytes (LIA)
  94.  * MAXRUN    length of run which shifts to next table (see below) (LIA)
  95.  * OVERFLOW    long-int arithmetic overflow must be avoided, will trap
  96.  * NOBUFFER    do not buffer hash-table i/o, B News locking is defective
  97.  */
  98.  
  99. #ifdef FUNNYSEEKS
  100. #include <unistd.h>
  101. #else
  102. #define    SEEK_SET    0
  103. #endif
  104. #ifdef OVERFLOW
  105. #include <limits.h>
  106. #endif
  107.  
  108. static int dbzversion = 3;    /* for validating .dir file format */
  109.  
  110. /*
  111.  * The dbz database exploits the fact that when news stores a <key,value>
  112.  * tuple, the `value' part is a seek offset into a text file, pointing to
  113.  * a copy of the `key' part.  This avoids the need to store a copy of
  114.  * the key in the dbz files.  However, the text file *must* exist and be
  115.  * consistent with the dbz files, or things will fail.
  116.  *
  117.  * The basic format of the database is a simple hash table containing the
  118.  * values.  A value is stored by indexing into the table using a hash value
  119.  * computed from the key; collisions are resolved by linear probing (just
  120.  * search forward for an empty slot, wrapping around to the beginning of
  121.  * the table if necessary).  Linear probing is a performance disaster when
  122.  * the table starts to get full, so a complication is introduced.  The
  123.  * database is actually one *or more* tables, stored sequentially in the
  124.  * .pag file, and the length of linear-probe sequences is limited.  The
  125.  * search (for an existing item or an empty slot) always starts in the
  126.  * first table, and whenever MAXRUN probes have been done in table N,
  127.  * probing continues in table N+1.  This behaves reasonably well even in
  128.  * cases of massive overflow.  There are some other small complications
  129.  * added, see comments below.
  130.  *
  131.  * The table size is fixed for any particular database, but is determined
  132.  * dynamically when a database is rebuilt.  The strategy is to try to pick
  133.  * the size so the first table will be no more than 2/3 full, that being
  134.  * slightly before the point where performance starts to degrade.  (It is
  135.  * desirable to be a bit conservative because the overflow strategy tends
  136.  * to produce files with holes in them, which is a nuisance.)
  137.  */
  138.  
  139. /*
  140.  * The following is for backward compatibility.
  141.  */
  142. #ifdef INDEX_SIZE
  143. #define    DEFSIZE    INDEX_SIZE
  144. #endif
  145. #include "ndbz.h"
  146.  
  147. /*
  148.  * We assume that unused areas of a binary file are zeros, and that the
  149.  * bit pattern of `(of_t)0' is all zeros.  The alternative is rather
  150.  * painful file initialization.  Note that okayvalue(), if OVERFLOW is
  151.  * defined, knows what value of an offset would cause overflow.
  152.  */
  153. #define    VACANT        ((of_t)0)
  154. #define    BIAS(o)        ((o)+1)        /* make any valid of_t non-VACANT */
  155. #define    UNBIAS(o)    ((o)-1)        /* reverse BIAS() effect */
  156.  
  157. /*
  158.  * In a Unix implementation, or indeed any in which an of_t is a byte
  159.  * count, there are a bunch of high bits free in an of_t.  There is a
  160.  * use for them.  Checking a possible hit by looking it up in the base
  161.  * file is relatively expensive, and the cost can be dramatically reduced
  162.  * by using some of those high bits to tag the value with a few more bits
  163.  * of the key's hash.  This detects most false hits without the overhead of
  164.  * seek+read+strcmp.  We use the top bit to indicate whether the value is
  165.  * tagged or not, and don't tag a value which is using the tag bits itself.
  166.  * We're in trouble if the of_t representation wants to use the top bit.
  167.  * The actual bitmasks and offset come from the configuration stuff,
  168.  * which permits fiddling with them as necessary, and also suppressing
  169.  * them completely (by defining the masks to 0).  We build pre-shifted
  170.  * versions of the masks for efficiency.
  171.  */
  172. #define    HASTAG(o)    ((o)&db->dbz_taghere)
  173. #define    TAG(o)        ((o)&db->dbz_tagbits)
  174. #define    NOTAG(o)    ((o)&~db->dbz_tagboth)
  175. #define    CANTAG(o)    (((o)&db->dbz_tagboth) == 0)
  176. #define    MKTAG(v)    (((v)<<db->dbz_conf.tagshift)&db->dbz_tagbits)
  177.  
  178. /*
  179.  * A new, from-scratch database, not built as a rebuild of an old one,
  180.  * needs to know table size and tagging.  Normally
  181.  * the user supplies this info, but there have to be defaults.
  182.  */
  183. #ifndef DEFSIZE
  184. #define    DEFSIZE    120011        /* 300007 might be better */
  185. #endif
  186. #ifndef NOTAGS
  187. #define    TAGENB    0x80        /* tag enable is top bit, tag is next 7 */
  188. #define    TAGMASK    0x7f
  189. #define    TAGSHIFT    24
  190. #else
  191. #define    TAGENB    0        /* no tags */
  192. #define    TAGMASK    0
  193. #define    TAGSHIFT    0
  194. #endif
  195.  
  196. static int getconf();
  197. static long getno();
  198. static int putconf();
  199. static void mybytemap();
  200. static of_t bytemap();
  201.  
  202. /* 
  203.  * For a program that makes many, many references to the database, it
  204.  * is a large performance win to keep the table in core, if it will fit.
  205.  * Note that this does hurt robustness in the event of crashes, and
  206.  * dbz_close() *must* be called to flush the in-core database to disk.
  207.  * The code is prepared to deal with the possibility that there isn't
  208.  * enough memory.  There *is* an assumption that a size_t is big enough
  209.  * to hold the size (in bytes) of one table, so dbz_open() tries to figure
  210.  * out whether this is possible first.
  211.  *
  212.  * The preferred way to ask for an in-core table is to do dbzincore(1)
  213.  * before dbz_open().  The default is not to do it, although -DINCORE
  214.  * overrides this for backward compatibility with old dbz.
  215.  *
  216.  * We keep only the first table in core.  This greatly simplifies the
  217.  * code, and bounds memory demand.  Furthermore, doing this is a large
  218.  * performance win even in the event of massive overflow.
  219.  */
  220. #ifdef INCORE
  221. static int default_incore = 1;
  222. #else
  223. static int default_incore = 0;
  224. #endif
  225.  
  226. #        ifndef MAXRUN
  227. #        define    MAXRUN    100
  228. #        endif
  229. static void start();
  230. #define    FRESH    ((struct searcher *)NULL)
  231. static of_t search();
  232. #define    NOTFOUND    ((of_t)-1)
  233. static int okayvalue();
  234. static int set();
  235.  
  236. /*
  237.  * Arguably the searcher struct for a given routine ought to be local to
  238.  * it, but a dbz_fetch() is very often immediately followed by a dbz_store(), and
  239.  * in some circumstances it is a useful performance win to remember where
  240.  * the dbz_fetch() completed.  So we use a global struct and remember whether
  241.  * it is current.
  242.  */
  243.  
  244. /* byte-ordering stuff */
  245. #define    MAPIN(o)    ((db->dbz_bytesame) ? (o) : bytemap((o), db->dbz_conf.bytemap, db->dbz_mybmap))
  246. #define    MAPOUT(o)    ((db->dbz_bytesame) ? (o) : bytemap((o), db->dbz_mybmap, db->dbz_conf.bytemap))
  247.  
  248. /* externals used */
  249. #ifndef __STDC__ /* avoid problemswith systems that declare atol as a macro */
  250. extern long atol();
  251. #endif
  252.  
  253. /* misc. forwards */
  254. static long hash();
  255. static void crcinit();
  256. static int isprime();
  257. static FILE *latebase();
  258.  
  259. /* file-naming stuff */
  260. static char dir[] = ".dir";
  261. static char pag[] = ".pag";
  262. static char *enstring();
  263.  
  264. /* central data structures */
  265. static of_t *getcore();
  266. static int putcore();
  267.  
  268. /*
  269.  - dbz_fresh - set up a new database, no historical info
  270.  */
  271. DBZ *                /* NULL for failure, !NULL for success */
  272. dbz_fresh(name, size, fs, tagmask)
  273. char *name;            /* base name; .dir and .pag must exist */
  274. long size;            /* table size (0 means default) */
  275. int fs;                /* field-separator character in base file */
  276. of_t tagmask;            /* 0 default, 1 no tags */
  277. {
  278.     register char *fn;
  279.     struct dbzconfig c;
  280.     register of_t m;
  281.     register FILE *f;
  282.  
  283.     if (size != 0 && size < 2) {
  284.         dprint(5, (debugfile, "dbz_fresh: preposterous size (%ld)\n", size));
  285.         return(NULL);
  286.     }
  287.  
  288.     /* get default configuration */
  289.     if (getconf((FILE *)NULL, (FILE *)NULL, &c) < 0)
  290.         return(NULL);    /* "can't happen" */
  291.  
  292.     /* and mess with it as specified */
  293.     if (size != 0)
  294.         c.tsize = size;
  295.     c.fieldsep = fs;
  296.     switch (tagmask) {
  297.     case 0:            /* default */
  298.         break;
  299.     case 1:            /* no tags */
  300.         c.tagshift = 0;
  301.         c.tagmask = 0;
  302.         c.tagenb = 0;
  303.         break;
  304.     default:
  305.         m = tagmask;
  306.         c.tagshift = 0;
  307.         while (!(m&01)) {
  308.             m >>= 1;
  309.             c.tagshift++;
  310.         }
  311.         c.tagmask = m;
  312.         c.tagenb = (m << 1) & ~m;
  313.         break;
  314.     }
  315.  
  316.     /* write it out */
  317.     fn = enstring(name, dir);
  318.     if (fn == NULL)
  319.         return(NULL);
  320.     f = fopen(fn, "w");
  321.     free(fn);
  322.     if (f == NULL) {
  323.         dprint(5, (debugfile, "dbz_fresh: unable to write config\n"));
  324.         return(NULL);
  325.     }
  326.     if (putconf(f, &c) < 0) {
  327.         (void) fclose(f);
  328.         return(NULL);
  329.     }
  330.     if (fclose(f) == EOF) {
  331.         dprint(5, (debugfile, "dbz_fresh: fclose failure\n"));
  332.         return(NULL);
  333.     }
  334.  
  335.     /* create/truncate .pag */
  336.     fn = enstring(name, pag);
  337.     if (fn == NULL)
  338.         return(NULL);
  339.     f = fopen(fn, "w");
  340.     free(fn);
  341.     if (f == NULL) {
  342.         dprint(5, (debugfile, "dbz_fresh: unable to create/truncate .pag file\n"));
  343.         return(NULL);
  344.     } else
  345.         (void) fclose(f);
  346.  
  347.     /* and punt to dbz_open for the hard work */
  348.     return(dbz_open(name, O_RDWR, 0));
  349. }
  350.  
  351. /*
  352.  - dbz_size - what's a good table size to hold this many entries?
  353.  */
  354. long
  355. dbzsize(contents)
  356. long contents;            /* 0 means what's the default */
  357. {
  358.     register long n;
  359.  
  360.     if (contents <= 0) {    /* foulup or default inquiry */
  361.         dprint(5, (debugfile, "dbzsize: preposterous input (%ld)\n", contents));
  362.         return(DEFSIZE);
  363.     }
  364.     n = (contents/2)*3;    /* try to keep table at most 2/3 full */
  365.     if (!(n&01))        /* make it odd */
  366.         n++;
  367.     dprint(5, (debugfile, "dbzsize: tentative size %ld\n", n));
  368.     while (!isprime(n))    /* and look for a prime */
  369.         n += 2;
  370.     dprint(5, (debugfile, "dbzsize: final size %ld\n", n));
  371.  
  372.     return(n);
  373. }
  374.  
  375. /*
  376.  - isprime - is a number prime?
  377.  *
  378.  * This is not a terribly efficient approach.
  379.  */
  380. static int            /* predicate */
  381. isprime(x)
  382. register long x;
  383. {
  384.     static int quick[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0 };
  385.     register int *ip;
  386.     register long div;
  387.     register long stop;
  388.  
  389.     /* hit the first few primes quickly to eliminate easy ones */
  390.     /* this incidentally prevents ridiculously small tables */
  391.     for (ip = quick; (div = *ip) != 0; ip++)
  392.         if (x%div == 0) {
  393.             dprint(5, (debugfile, "isprime: quick result on %ld\n", (long)x));
  394.             return(0);
  395.         }
  396.  
  397.     /* approximate square root of x */
  398.     for (stop = x; x/stop < stop; stop >>= 1)
  399.         continue;
  400.     stop <<= 1;
  401.  
  402.     /* try odd numbers up to stop */
  403.     for (div = *--ip; div < stop; div += 2)
  404.         if (x%div == 0)
  405.             return(0);
  406.  
  407.     return(1);
  408. }
  409.  
  410. /*
  411.  - dbz_again - set up a new database to be a rebuild of an old one
  412.  */
  413. DBZ *                /* NULL for failure, !NULL for success */
  414. dbz_again(name, oldname)
  415. char *name;            /* base name; .dir and .pag must exist */
  416. char *oldname;            /* base name; all must exist */
  417. {
  418.     register char *fn;
  419.     struct dbzconfig c;
  420.     register int i;
  421.     register long top;
  422.     register FILE *f;
  423.     register int newtable;
  424.     register of_t newsize;
  425.  
  426.     /* pick up the old configuration */
  427.     fn = enstring(oldname, dir);
  428.     if (fn == NULL)
  429.         return(NULL);
  430.     f = fopen(fn, "r");
  431.     free(fn);
  432.     if (f == NULL) {
  433.         dprint(5, (debugfile, "dbz_again: cannot open old .dir file\n"));
  434.         return(NULL);
  435.     }
  436.     i = getconf(f, (FILE *)NULL, &c);
  437.     (void) fclose(f);
  438.     if (i < 0) {
  439.         dprint(5, (debugfile, "dbz_again: getconf failed\n"));
  440.         return(NULL);
  441.     }
  442.  
  443.     /* tinker with it */
  444.     top = 0;
  445.     newtable = 0;
  446.     for (i = 0; i < NUSEDS; i++) {
  447.         if (top < c.used[i])
  448.             top = c.used[i];
  449.         if (c.used[i] == 0)
  450.             newtable = 1;    /* hasn't got full usage history yet */
  451.     }
  452.     if (top == 0) {
  453.         dprint(5, (debugfile, "dbz_again: old table has no contents!\n"));
  454.         newtable = 1;
  455.     }
  456.     for (i = NUSEDS-1; i > 0; i--)
  457.         c.used[i] = c.used[i-1];
  458.     c.used[0] = 0;
  459.     newsize = dbzsize(top);
  460.     if (!newtable || newsize > c.tsize)    /* don't shrink new table */
  461.         c.tsize = newsize;
  462.  
  463.     /* write it out */
  464.     fn = enstring(name, dir);
  465.     if (fn == NULL)
  466.         return(NULL);
  467.     f = fopen(fn, "w");
  468.     free(fn);
  469.     if (f == NULL) {
  470.         dprint(5, (debugfile, "dbz_again: unable to write new .dir\n"));
  471.         return(NULL);
  472.     }
  473.     i = putconf(f, &c);
  474.     (void) fclose(f);
  475.     if (i < 0) {
  476.         dprint(5, (debugfile, "dbz_again: putconf failed\n"));
  477.         return(NULL);
  478.     }
  479.  
  480.     /* create/truncate .pag */
  481.     fn = enstring(name, pag);
  482.     if (fn == NULL)
  483.         return(NULL);
  484.     f = fopen(fn, "w");
  485.     free(fn);
  486.     if (f == NULL) {
  487.         dprint(5, (debugfile, "dbz_again: unable to create/truncate .pag file\n"));
  488.         return(NULL);
  489.     } else
  490.         (void) fclose(f);
  491.  
  492.     /* and let dbz_open do the work */
  493.     return(dbz_open(name, O_RDWR, 0));
  494. }
  495.  
  496. /*
  497.  - dbz_open - open a database, creating it (using defaults) if necessary
  498.  *
  499.  * We try to leave errno set plausibly, to the extent that underlying
  500.  * functions permit this, since many people consult it if dbz_open() fails.
  501.  */
  502. DBZ *                /* NULL for failure, !NULL for success */
  503. dbz_open(name, mode, flags)
  504. char *name;
  505. int mode, flags;
  506. {
  507.     register int i;
  508.     register size_t s;
  509.     register DBZ  *db;
  510.     register char *dirfname;
  511.     register char *pagfname;
  512.  
  513.     if ((db = (DBZ *) calloc(sizeof(DBZ), 1)) == NULL) {
  514.         dprint(5, (debugfile, "dbz_open: no room for DBZ structure\n"));
  515.         return(NULL);
  516.     }
  517.     /* open the .dir file */
  518.     dirfname = enstring(name, dir);
  519.     if (dirfname == NULL)
  520.         return(NULL);
  521.  
  522.     if (mode == O_RDONLY) {
  523.         db->dbz_dirf = fopen(dirfname, "r");
  524.         db->dbz_dirronly = 1;
  525.     } else
  526.         db->dbz_dirf = fopen(dirfname, "r+");
  527.     free(dirfname);
  528.     if (db->dbz_dirf == NULL) {
  529.         dprint(5, (debugfile, "dbz_open: can't open .dir file\n"));
  530.         return(NULL);
  531.     }
  532.  
  533.     /* open the .pag file */
  534.     pagfname = enstring(name, pag);
  535.     if (pagfname == NULL) {
  536.         (void) fclose(db->dbz_dirf);
  537.         return(NULL);
  538.     }
  539.     if (mode == O_RDONLY) {
  540.         db->dbz_pagf = fopen(pagfname, "rb");
  541.         db->dbz_pagronly = 1;
  542.     } else
  543.         db->dbz_pagf = fopen(pagfname, "r+b");
  544.  
  545.     if (db->dbz_pagf == NULL) {
  546.         dprint(5, (debugfile, "dbz_open: .pag open failed\n"));
  547.         (void) fclose(db->dbz_dirf);
  548.         free(pagfname);
  549.         return(NULL);
  550.     }
  551. #ifdef NOBUFFER
  552.     /*
  553.      * B News does not do adequate locking on its database accesses.
  554.      * Why it doesn't get into trouble using dbm is a mystery.  In any
  555.      * case, doing unbuffered i/o does not cure the problem, but does
  556.      * enormously reduce its incidence.
  557.      */
  558.     (void) setbuf(db->dbz_pagf, (char *)NULL);
  559. #else
  560. #ifdef _IOFBF
  561.     (void) setvbuf(db->dbz_pagf, (char *)db->dbz_pagbuf, _IOFBF, sizeof(db->dbz_pagbuf));
  562. #endif
  563. #endif
  564.     db->dbz_pagpos = -1;
  565.     /* don't free pagfname, need it below */
  566.  
  567.     /* open the base file */
  568.     db->dbz_basef = fopen(name, "r");
  569.     if (db->dbz_basef == NULL) {
  570.         dprint(5, (debugfile, "dbz_open: basefile open failed\n"));
  571.         db->dbz_basefname = enstring(name, "");
  572.         if (db->dbz_basefname == NULL) {
  573.             (void) fclose(db->dbz_pagf);
  574.             (void) fclose(db->dbz_dirf);
  575.             free(pagfname);
  576.             return(NULL);
  577.         }
  578.     } else
  579.         db->dbz_basefname = NULL;
  580. #ifdef _IOFBF
  581.     if (db->dbz_basef != NULL)
  582.         (void) setvbuf(db->dbz_basef, db->dbz_basebuf, _IOFBF, sizeof(db->dbz_basebuf));
  583. #endif
  584.  
  585.     /* pick up configuration */
  586.     if (getconf(db->dbz_dirf, db->dbz_pagf, &db->dbz_conf) < 0) {
  587.         dprint(5, (debugfile, "dbz_open: getconf failure\n"));
  588.         (void) fclose(db->dbz_basef);
  589.         (void) fclose(db->dbz_pagf);
  590.         (void) fclose(db->dbz_basef);
  591.         (void) fclose(db->dbz_dirf);
  592.         free(pagfname);
  593.         errno = EDOM;    /* kind of a kludge, but very portable */
  594.         return(NULL);
  595.     }
  596.     db->dbz_tagbits = db->dbz_conf.tagmask << db->dbz_conf.tagshift;
  597.     db->dbz_taghere = db->dbz_conf.tagenb << db->dbz_conf.tagshift;
  598.     db->dbz_tagboth = db->dbz_tagbits | db->dbz_taghere;
  599.     mybytemap(db->dbz_mybmap);
  600.     db->dbz_bytesame = 1;
  601.     for (i = 0; i < SOF; i++)
  602.         if (db->dbz_mybmap[i] != db->dbz_conf.bytemap[i])
  603.             db->dbz_bytesame = 0;
  604.  
  605.     /* get first table into core, if it looks desirable and feasible */
  606.     s = (size_t)db->dbz_conf.tsize * SOF;
  607.     db->dbz_incore = default_incore;
  608.     if (db->dbz_incore && (of_t)(s/SOF) == db->dbz_conf.tsize) {
  609.         db->dbz_bufpagf = fopen(pagfname, (db->dbz_pagronly) ? "rb" : "r+b");
  610.         if (db->dbz_bufpagf != NULL)
  611.             db->dbz_corepag = getcore(db);
  612.     } else {
  613.         db->dbz_bufpagf = NULL;
  614.         db->dbz_corepag = NULL;
  615.     }
  616.     free(pagfname);
  617.  
  618.     /* misc. setup */
  619.     crcinit();
  620.     db->dbz_written = 0;
  621.     db->dbz_prevp = FRESH;
  622.     dprint(5, (debugfile, "dbz_open: succeeded\n"));
  623.     return(db);
  624. }
  625.  
  626. /*
  627.  - enstring - concatenate two strings into a malloced area
  628.  */
  629. static char *            /* NULL if malloc fails */
  630. enstring(s1, s2)
  631. char *s1;
  632. char *s2;
  633. {
  634.     register char *p;
  635.  
  636.     p = malloc((size_t)strlen(s1) + (size_t)strlen(s2) + 1);
  637.     if (p != NULL) {
  638.         (void) strcpy(p, s1);
  639.         (void) strcat(p, s2);
  640.     } else {
  641.         dprint(5, (debugfile, "enstring(%s, %s) out of memory\n", s1, s2));
  642.     }
  643.     return(p);
  644. }
  645.  
  646. /*
  647.  - dbz_close - close a database
  648.  */
  649. int
  650. dbz_close(db)
  651. register DBZ *db;
  652. {
  653.     register int ret = 0;
  654.  
  655.     if (db->dbz_pagf == NULL) {
  656.         dprint(5, (debugfile, "dbz_close: not opened!\n"));
  657.         return(-1);
  658.     }
  659.  
  660.     if (fclose(db->dbz_pagf) == EOF) {
  661.         dprint(5, (debugfile, "dbz_close: fclose(pagf) failed\n"));
  662.         ret = -1;
  663.     }
  664.     if (dbz_sync(db) < 0)
  665.         ret = -1;
  666.     if (db->dbz_bufpagf != NULL && fclose(db->dbz_bufpagf) == EOF) {
  667.         dprint(5, (debugfile, "dbz_close: fclose(bufpagf) failed\n"));
  668.         ret = -1;
  669.     }
  670.     if (db->dbz_corepag != NULL)
  671.         free((char *)db->dbz_corepag);
  672.     db->dbz_corepag = NULL;
  673.     if (fclose(db->dbz_basef) == EOF) {
  674.         dprint(5, (debugfile, "dbz_close: fclose(basef) failed\n"));
  675.         ret = -1;
  676.     }
  677.     if (db->dbz_basefname != NULL)
  678.         free(db->dbz_basefname);
  679.     db->dbz_basef = NULL;
  680.     db->dbz_pagf = NULL;
  681.     if (fclose(db->dbz_dirf) == EOF) {
  682.         dprint(5, (debugfile, "dbz_close: fclose(dirf) failed\n"));
  683.         ret = -1;
  684.     }
  685.  
  686.     free((char *) db);
  687.  
  688.     dprint(5, (debugfile, "dbz_close: %s\n", (ret == 0) ? "succeeded" : "failed"));
  689.     return(ret);
  690. }
  691.  
  692. /*
  693.  - dbz_sync - push all in-core data out to disk
  694.  */
  695. int
  696. dbz_sync(db)
  697. register DBZ *db;
  698. {
  699.     register int ret = 0;
  700.  
  701.     if (db->dbz_pagf == NULL) {
  702.         dprint(5, (debugfile, "dbzsync: not opened!\n"));
  703.         return(-1);
  704.     }
  705.     if (!db->dbz_written)
  706.         return(0);
  707.  
  708.     if (db->dbz_corepag != NULL) {
  709.         if (putcore(db) < 0) {
  710.             dprint(5, (debugfile, "dbzsync: putcore failed\n"));
  711.             ret = -1;
  712.         }
  713.     }
  714.     if (!db->dbz_conf.olddbz)
  715.         if (putconf(db->dbz_dirf, &db->dbz_conf) < 0)
  716.             ret = -1;
  717.  
  718.     dprint(5, (debugfile, "dbzsync: %s\n", (ret == 0) ? "succeeded" : "failed"));
  719.     return(ret);
  720. }
  721.  
  722. /*
  723.  - dbzcancel - cancel writing of in-core data
  724.  * Mostly for use from child processes.
  725.  * Note that we don't need to futz around with stdio buffers, because we
  726.  * always fflush them immediately anyway and so they never have stale data.
  727.  */
  728. int
  729. dbz_cancel(db)
  730. register DBZ *db;
  731. {
  732.     if (db->dbz_pagf == NULL) {
  733.         dprint(5, (debugfile, "dbz_cancel: not opened!\n"));
  734.         return(-1);
  735.     }
  736.  
  737.     db->dbz_written = 0;
  738.     return(0);
  739. }
  740.  
  741. /*
  742.  - dbz_fetch - get an entry from the database
  743.  *
  744.  * Disgusting fine point, in the name of backward compatibility:  if the
  745.  * last character of "key" is a NUL, that character is (effectively) not
  746.  * part of the comparison against the stored keys.
  747.  */
  748. datum                /* dptr NULL, dsize 0 means failure */
  749. dbz_fetch(db, key)
  750. register DBZ *db;
  751. datum key;
  752. {
  753.     char buffer[DBZMAXKEY + 1];
  754.     static of_t key_ptr;        /* return value points here */
  755.     datum output;
  756.     register size_t keysize;
  757.     register size_t cmplen;
  758.     register char *sepp;
  759.  
  760.     dprint(5, (debugfile, "dbz_fetch: (%s)\n", key.dptr));
  761.     output.dptr = NULL;
  762.     output.dsize = 0;
  763.     db->dbz_prevp = FRESH;
  764.  
  765.     /* Key is supposed to be less than DBZMAXKEY */
  766.     keysize = key.dsize;
  767.     if (keysize >= DBZMAXKEY) {
  768.         keysize = DBZMAXKEY;
  769.         dprint(5, (debugfile, "keysize is %d - truncated to %d\n", key.dsize, DBZMAXKEY));
  770.     }
  771.  
  772.     if (db->dbz_pagf == NULL) {
  773.         dprint(5, (debugfile, "dbz_fetch: database not open!\n"));
  774.         return(output);
  775.     } else if (db->dbz_basef == NULL) {    /* basef didn't exist yet */
  776.         db->dbz_basef = latebase(db);
  777.         if (db->dbz_basef == NULL)
  778.             return(output);
  779.     }
  780.  
  781.     cmplen = keysize;
  782.     sepp = &db->dbz_conf.fieldsep;
  783.     if (key.dptr[keysize-1] == '\0') {
  784.         cmplen--;
  785.         sepp = &buffer[keysize-1];
  786.     }
  787.     start(db, &key, FRESH);
  788.     while ((key_ptr = search(db)) != NOTFOUND) {
  789.         dprint(5, (debugfile, "got 0x%lx\n", key_ptr));
  790.  
  791.         /* fetch the key */
  792.         if (fseek(db->dbz_basef, key_ptr, SEEK_SET) != 0) {
  793.             dprint(5, (debugfile, "dbz_fetch: seek failed\n"));
  794.             return(output);
  795.         }
  796.         if (fread(buffer, 1, keysize, db->dbz_basef) != keysize) {
  797.             dprint(5, (debugfile, "dbz_fetch: read failed\n"));
  798.             return(output);
  799.         }
  800.  
  801.         /* try it */
  802.         buffer[keysize] = '\0';        /* terminated for DEBUG */
  803.         dprint(5, (debugfile, "dbz_fetch: buffer (%s) looking for (%s) size = %d\n", 
  804.                         buffer, key.dptr, keysize));
  805.         if (bcmp(key.dptr, buffer, cmplen) == 0 &&
  806.                 (*sepp == db->dbz_conf.fieldsep || *sepp == '\0')) {
  807.             /* we found it */
  808.             output.dptr = (char *)&key_ptr;
  809.             output.dsize = SOF;
  810.             dprint(5, (debugfile, "dbz_fetch: successful\n"));
  811.             return(output);
  812.         }
  813.     }
  814.  
  815.     /* we didn't find it */
  816.     dprint(5, (debugfile, "dbz_fetch: failed\n"));
  817.     db->dbz_prevp = &db->dbz_srch;            /* remember where we stopped */
  818.     return(output);
  819. }
  820.  
  821. /*
  822.  - latebase - try to open a base file that wasn't there at the start
  823.  */
  824. static FILE *
  825. latebase(db)
  826. register DBZ *db;
  827. {
  828.     register FILE *it;
  829.  
  830.     if (db->dbz_basefname == NULL) {
  831.         dprint(5, (debugfile, "latebase: name foulup\n"));
  832.         return(NULL);
  833.     }
  834.     it = fopen(db->dbz_basefname, "r");
  835.     if (it == NULL) {
  836.         dprint(5, (debugfile, "latebase: still can't open base\n"));
  837.     } else {
  838.         dprint(5, (debugfile, "latebase: late open succeeded\n"));
  839.         free(db->dbz_basefname);
  840.         db->dbz_basefname = NULL;
  841. #ifdef _IOFBF
  842.         (void) setvbuf(it, db->dbz_basebuf, _IOFBF, sizeof(db->dbz_basebuf));
  843. #endif
  844.     }
  845.     return(it);
  846. }
  847.  
  848. /*
  849.  - dbz_store - add an entry to the database
  850.  */
  851. int                /* 0 success, -1 failure */
  852. dbz_store(db, key, data)
  853. register DBZ *db;
  854. datum key;
  855. datum data;
  856. {
  857.     of_t value;
  858.  
  859.     if (db->dbz_pagf == NULL) {
  860.         dprint(5, (debugfile, "dbz_store: database not open!\n"));
  861.         return(-1);
  862.     } else if (db->dbz_basef == NULL) {    /* basef didn't exist yet */
  863.         db->dbz_basef = latebase(db);
  864.         if (db->dbz_basef == NULL)
  865.             return(-1);
  866.     }
  867.     if (db->dbz_pagronly) {
  868.         dprint(5, (debugfile, "dbz_store: database open read-only\n"));
  869.         return(-1);
  870.     }
  871.     if (data.dsize != SOF) {
  872.         dprint(5, (debugfile, "dbz_store: value size wrong (%d)\n", data.dsize));
  873.         return(-1);
  874.     }
  875.     if (key.dsize >= DBZMAXKEY) {
  876.         dprint(5, (debugfile, "dbz_store: key size too big (%d)\n", key.dsize));
  877.         return(-1);
  878.     }
  879.  
  880.     /* copy the value in to ensure alignment */
  881.     (void) bcopy(data.dptr, (char *)&value, SOF);
  882.     dprint(5, (debugfile, "dbz_store: (%s, %ld)\n", key.dptr, (long)value));
  883.     if (!okayvalue(db, value)) {
  884.         dprint(5, (debugfile, "dbz_store: reserved bit or overflow in 0x%lx\n", value));
  885.         return(-1);
  886.     }
  887.  
  888.     /* find the place, exploiting previous search if possible */
  889.     start(db, &key, db->dbz_prevp);
  890.     while (search(db) != NOTFOUND)
  891.         continue;
  892.  
  893.     db->dbz_prevp = FRESH;
  894.     db->dbz_conf.used[0]++;
  895.     dprint(5, (debugfile, "dbz_store: used count %ld\n", db->dbz_conf.used[0]));
  896.     db->dbz_written = 1;
  897.     return(set(db, value));
  898. }
  899.  
  900. /*
  901.  - dbz_incore - control attempts to keep .pag file in core
  902.  */
  903. int                /* old setting */
  904. dbz_incore(value)
  905. int value;
  906. {
  907.     register int old = default_incore;
  908.  
  909.     default_incore = value;
  910.     return(old);
  911. }
  912.  
  913. /*
  914.  - getconf - get configuration from .dir file
  915.  */
  916. static int            /* 0 success, -1 failure */
  917. getconf(df, pf, cp)
  918. register FILE *df;        /* NULL means just give me the default */
  919. register FILE *pf;        /* NULL means don't care about .pag */
  920. register struct dbzconfig *cp;
  921. {
  922.     register int c;
  923.     register int i;
  924.     int err = 0;
  925.  
  926.     c = (df != NULL) ? getc(df) : EOF;
  927.     if (c == EOF) {        /* empty file, no configuration known */
  928.         cp->olddbz = 0;
  929.         if (df != NULL && pf != NULL && getc(pf) != EOF)
  930.             cp->olddbz = 1;
  931.         cp->tsize = DEFSIZE;
  932.         cp->fieldsep = '\t';
  933.         for (i = 0; i < NUSEDS; i++)
  934.             cp->used[i] = 0;
  935.         cp->valuesize = SOF;
  936.         mybytemap(cp->bytemap);
  937.         cp->tagenb = TAGENB;
  938.         cp->tagmask = TAGMASK;
  939.         cp->tagshift = TAGSHIFT;
  940.         dprint(5, (debugfile, "getconf: defaults (%ld, (0x%lx/0x%lx<<%d))\n",
  941.             cp->tsize, cp->tagenb, cp->tagmask, cp->tagshift));
  942.         return(0);
  943.     }
  944.     (void) ungetc(c, df);
  945.  
  946.     /* first line, the vital stuff */
  947.     if (getc(df) != 'd' || getc(df) != 'b' || getc(df) != 'z')
  948.         err = -1;
  949.     if (getno(df, &err) != dbzversion)
  950.         err = -1;
  951.     cp->tsize = getno(df, &err);
  952.     cp->fieldsep = getno(df, &err);
  953.     while ((c = getc(df)) == ' ')
  954.         continue;
  955.     cp->tagenb = getno(df, &err);
  956.     cp->tagmask = getno(df, &err);
  957.     cp->tagshift = getno(df, &err);
  958.     cp->valuesize = getno(df, &err);
  959.     if (cp->valuesize != SOF) {
  960.         dprint(5, (debugfile, "getconf: wrong of_t size (%d)\n", cp->valuesize));
  961.         err = -1;
  962.         cp->valuesize = SOF;    /* to protect the loops below */
  963.     }
  964.     for (i = 0; i < cp->valuesize; i++)
  965.         cp->bytemap[i] = getno(df, &err);
  966.     if (getc(df) != '\n')
  967.         err = -1;
  968.     dprint(5, (debugfile, "size %ld, sep %d, tags 0x%lx/0x%lx<<%d, ", cp->tsize,
  969.             cp->fieldsep, cp->tagenb, cp->tagmask, cp->tagshift));
  970.     dprint(5, (debugfile, "bytemap (%d)", cp->valuesize));
  971.     for (i = 0; i < cp->valuesize; i++) {
  972.         dprint(5, (debugfile, " %d", cp->bytemap[i]));
  973.     }
  974.     dprint(5, (debugfile, "\n"));
  975.  
  976.     /* second line, the usages */
  977.     for (i = 0; i < NUSEDS; i++)
  978.         cp->used[i] = getno(df, &err);
  979.     if (getc(df) != '\n')
  980.         err = -1;
  981.     dprint(5, (debugfile, "used %ld %ld %ld...\n", cp->used[0], cp->used[1], cp->used[2]));
  982.  
  983.     if (err < 0) {
  984.         dprint(5, (debugfile, "getconf error\n"));
  985.         return(-1);
  986.     }
  987.     return(0);
  988. }
  989.  
  990. /*
  991.  - getno - get a long
  992.  */
  993. static long
  994. getno(f, ep)
  995. FILE *f;
  996. int *ep;
  997. {
  998.     register char *p;
  999. #    define    MAXN    50
  1000.     char getbuf[MAXN];
  1001.     register int c;
  1002.  
  1003.     while ((c = getc(f)) == ' ')
  1004.         continue;
  1005.     if (c == EOF || c == '\n') {
  1006.         dprint(5, (debugfile, "getno: missing number\n"));
  1007.         *ep = -1;
  1008.         return(0);
  1009.     }
  1010.     p = getbuf;
  1011.     *p++ = c;
  1012.     while ((c = getc(f)) != EOF && c != '\n' && c != ' ')
  1013.         if (p < &getbuf[MAXN-1])
  1014.             *p++ = c;
  1015.     if (c == EOF) {
  1016.         dprint(5, (debugfile, "getno: EOF\n"));
  1017.         *ep = -1;
  1018.     } else
  1019.         (void) ungetc(c, f);
  1020.     *p = '\0';
  1021.  
  1022.     if (strspn(getbuf, "-1234567890") != strlen(getbuf)) {
  1023.         dprint(5, (debugfile, "getno: `%s' non-numeric\n", getbuf));
  1024.         *ep = -1;
  1025.     }
  1026.     return(atol(getbuf));
  1027. }
  1028.  
  1029. /*
  1030.  - putconf - write configuration to .dir file
  1031.  */
  1032. static int            /* 0 success, -1 failure */
  1033. putconf(f, cp)
  1034. register FILE *f;
  1035. register struct dbzconfig *cp;
  1036. {
  1037.     register int i;
  1038.     register int ret = 0;
  1039.  
  1040.     if (fseek(f, (of_t)0, SEEK_SET) != 0) {
  1041.         dprint(5, (debugfile, "fseek failure in putconf\n"));
  1042.         ret = -1;
  1043.     }
  1044.     fprintf(f, "dbz %d %ld %d %ld %ld %d %d", dbzversion, cp->tsize,
  1045.                 cp->fieldsep, cp->tagenb,
  1046.                 cp->tagmask, cp->tagshift, cp->valuesize);
  1047.     for (i = 0; i < cp->valuesize; i++)
  1048.         fprintf(f, " %d", cp->bytemap[i]);
  1049.     fprintf(f, "\n");
  1050.     for (i = 0; i < NUSEDS; i++)
  1051.         fprintf(f, "%ld%c", cp->used[i], (i < NUSEDS-1) ? ' ' : '\n');
  1052.  
  1053.     (void) fflush(f);
  1054.     if (ferror(f))
  1055.         ret = -1;
  1056.  
  1057.     dprint(5, (debugfile, "putconf status %d\n", ret));
  1058.     return(ret);
  1059. }
  1060.  
  1061. /*
  1062.  - getcore - try to set up an in-core copy of .pag file
  1063.  */
  1064. static of_t *            /* pointer to copy, or NULL */
  1065. getcore(db)
  1066. register DBZ *db;
  1067. {
  1068.     register of_t *p;
  1069.     register size_t i;
  1070.     register size_t nread;
  1071.     register char *it;
  1072.  
  1073.     it = malloc((size_t)db->dbz_conf.tsize * SOF);
  1074.     if (it == NULL) {
  1075.         dprint(5, (debugfile, "getcore: malloc failed\n"));
  1076.         return(NULL);
  1077.     }
  1078.  
  1079.     nread = fread(it, SOF, (size_t)db->dbz_conf.tsize, db->dbz_bufpagf);
  1080.     if (ferror(db->dbz_bufpagf)) {
  1081.         dprint(5, (debugfile, "getcore: read failed\n"));
  1082.         free(it);
  1083.         return(NULL);
  1084.     }
  1085.  
  1086.     p = (of_t *)it + nread;
  1087.     i = (size_t)db->dbz_conf.tsize - nread;
  1088.     while (i-- > 0)
  1089.         *p++ = VACANT;
  1090.     return((of_t *)it);
  1091. }
  1092.  
  1093. /*
  1094.  - putcore - try to rewrite an in-core table
  1095.  */
  1096. static int            /* 0 okay, -1 fail */
  1097. putcore(db)
  1098. register DBZ *db;
  1099. {
  1100.     if (fseek(db->dbz_bufpagf, (of_t)0, SEEK_SET) != 0) {
  1101.         dprint(5, (debugfile, "fseek failure in putcore\n"));
  1102.         return(-1);
  1103.     }
  1104.     (void) fwrite((char *)db->dbz_corepag, SOF, (size_t)db->dbz_conf.tsize, db->dbz_bufpagf);
  1105.     (void) fflush(db->dbz_bufpagf);
  1106.     return((ferror(db->dbz_bufpagf)) ? -1 : 0);
  1107. }
  1108.  
  1109. /*
  1110.  - start - set up to start or restart a search
  1111.  */
  1112. static void
  1113. start(db, kp, osp)
  1114. register DBZ *db;
  1115. register datum *kp;
  1116. register struct searcher *osp;        /* may be FRESH, i.e. NULL */
  1117. {
  1118.     register struct searcher *sp = &db->dbz_srch;
  1119.     register long h;
  1120.  
  1121.     h = hash(kp->dptr, kp->dsize);
  1122.     if (osp != FRESH && osp->hash == h) {
  1123.         if (sp != osp)
  1124.             *sp = *osp;
  1125.         dprint(5, (debugfile, "search restarted\n"));
  1126.     } else {
  1127.         sp->hash = h;
  1128.         sp->tag = MKTAG(h / db->dbz_conf.tsize);
  1129.         dprint(5, (debugfile, "tag 0x%lx\n", sp->tag));
  1130.         sp->place = h % db->dbz_conf.tsize;
  1131.         sp->tabno = 0;
  1132.         sp->run = (db->dbz_conf.olddbz) ? db->dbz_conf.tsize : MAXRUN;
  1133.         sp->aborted = 0;
  1134.     }
  1135.     sp->seen = 0;
  1136. }
  1137.  
  1138. /*
  1139.  - search - conduct part of a search
  1140.  */
  1141. static of_t            /* NOTFOUND if we hit VACANT or error */
  1142. search(db)
  1143. register DBZ *db;
  1144. {
  1145.     register struct searcher *sp = &db->dbz_srch;
  1146.     register of_t dest;
  1147.     register of_t value;
  1148.     of_t val;        /* buffer for value (can't fread register) */
  1149.     register of_t place;
  1150.  
  1151.     if (sp->aborted)
  1152.         return(NOTFOUND);
  1153.  
  1154.     for (;;) {
  1155.         /* determine location to be examined */
  1156.         place = sp->place;
  1157.         if (sp->seen) {
  1158.             /* go to next location */
  1159.             if (--sp->run <= 0) {
  1160.                 sp->tabno++;
  1161.                 sp->run = MAXRUN;
  1162.             }
  1163.             place = (place+1)%db->dbz_conf.tsize + sp->tabno*db->dbz_conf.tsize;
  1164.             sp->place = place;
  1165.         } else
  1166.             sp->seen = 1;    /* now looking at current location */
  1167.         dprint(5, (debugfile, "search @ %ld\n", place));
  1168.  
  1169.         /* get the tagged value */
  1170.         if (db->dbz_corepag != NULL && place < db->dbz_conf.tsize) {
  1171.             dprint(5, (debugfile, "search: in core\n"));
  1172.             value = MAPIN(db->dbz_corepag[place]);
  1173.         } else {
  1174.             /* seek, if necessary */
  1175.             dest = place * SOF;
  1176.             if (db->dbz_pagpos != dest) {
  1177.                 if (fseek(db->dbz_pagf, dest, SEEK_SET) != 0) {
  1178.                     dprint(5, (debugfile, "search: seek failed\n"));
  1179.                     db->dbz_pagpos = -1;
  1180.                     sp->aborted = 1;
  1181.                     return(NOTFOUND);
  1182.                 }
  1183.                 db->dbz_pagpos = dest;
  1184.             }
  1185.  
  1186.             /* read it */
  1187.             if (fread((char *)&val, sizeof(val), 1, db->dbz_pagf) == 1)
  1188.                 value = MAPIN(val);
  1189.             else if (ferror(db->dbz_pagf)) {
  1190.                 dprint(5, (debugfile, "search: read failed\n"));
  1191.                 db->dbz_pagpos = -1;
  1192.                 sp->aborted = 1;
  1193.                 return(NOTFOUND);
  1194.             } else
  1195.                 value = VACANT;
  1196.  
  1197.             /* and finish up */
  1198.             db->dbz_pagpos += sizeof(val);
  1199.         }
  1200.  
  1201.         /* vacant slot is always cause to return */
  1202.         if (value == VACANT) {
  1203.             dprint(5, (debugfile, "search: empty slot\n"));
  1204.             return(NOTFOUND);
  1205.         };
  1206.  
  1207.         /* check the tag */
  1208.         value = UNBIAS(value);
  1209.         dprint(5, (debugfile, "got 0x%lx\n", value));
  1210.         if (!HASTAG(value)) {
  1211.             dprint(5, (debugfile, "tagless\n"));
  1212.             return(value);
  1213.         } else if ((TAG(value) == sp->tag) || db->dbz_taghere) {
  1214.             dprint(5, (debugfile, "match\n"));
  1215.             return(NOTAG(value));
  1216.         } else {
  1217.             dprint(5, (debugfile, "mismatch 0x%lx\n", TAG(value)));
  1218.         }
  1219.     }
  1220.     /* NOTREACHED */
  1221. }
  1222.  
  1223. /*
  1224.  - okayvalue - check that a value can be stored
  1225.  */
  1226. static int            /* predicate */
  1227. okayvalue(db, value)
  1228. register DBZ *db;
  1229. of_t value;
  1230. {
  1231.     if (HASTAG(value))
  1232.         return(0);
  1233. #ifdef OVERFLOW
  1234.     if (value == LONG_MAX)    /* BIAS() and UNBIAS() will overflow */
  1235.         return(0);
  1236. #endif
  1237.     return(1);
  1238. }
  1239.  
  1240. /*
  1241.  - set - store a value into a location previously found by search
  1242.  */
  1243. static int            /* 0 success, -1 failure */
  1244. set(db, value)
  1245. register DBZ *db;
  1246. of_t value;
  1247. {
  1248.     register struct searcher *sp  = &db->dbz_srch;
  1249.     register of_t place = sp->place;
  1250.     register of_t v = value;
  1251.  
  1252.     if (sp->aborted)
  1253.         return(-1);
  1254.  
  1255.     if (CANTAG(v) && !db->dbz_conf.olddbz) {
  1256.         v |= sp->tag | db->dbz_taghere;
  1257.         if (v != UNBIAS(VACANT))    /* BIAS(v) won't look VACANT */
  1258. #ifdef OVERFLOW
  1259.             if (v != LONG_MAX)    /* and it won't overflow */
  1260. #endif
  1261.             value = v;
  1262.     }
  1263.     dprint(5, (debugfile, "tagged value is 0x%lx\n", value));
  1264.     value = BIAS(value);
  1265.     value = MAPOUT(value);
  1266.  
  1267.     /* If we have the index file in memory, use it */
  1268.     if (db->dbz_corepag != NULL && place < db->dbz_conf.tsize) {
  1269.         db->dbz_corepag[place] = value;
  1270.         dprint(5, (debugfile, "set: incore\n"));
  1271.         return(0);
  1272.     }
  1273.  
  1274.     /* seek to spot */
  1275.     db->dbz_pagpos = -1;        /* invalidate position memory */
  1276.     if (fseek(db->dbz_pagf, place * SOF, SEEK_SET) != 0) {
  1277.         dprint(5, (debugfile, "set: seek failed\n"));
  1278.         sp->aborted = 1;
  1279.         return(-1);
  1280.     }
  1281.  
  1282.     /* write in data */
  1283.     if (fwrite((char *)&value, SOF, 1, db->dbz_pagf) != 1) {
  1284.         dprint(5, (debugfile, "set: write failed\n"));
  1285.         sp->aborted = 1;
  1286.         return(-1);
  1287.     }
  1288.     /* fflush improves robustness, and buffer re-use is rare anyway */
  1289.     if (fflush(db->dbz_pagf) == EOF) {
  1290.         dprint(5, (debugfile, "set: fflush failed\n"));
  1291.         sp->aborted = 1;
  1292.         return(-1);
  1293.     }
  1294.  
  1295.     dprint(5, (debugfile, "set: succeeded\n"));
  1296.     return(0);
  1297. }
  1298.  
  1299. /*
  1300.  - mybytemap - determine this machine's byte map
  1301.  *
  1302.  * A byte map is an array of ints, sizeof(of_t) of them.  The 0th int
  1303.  * is the byte number of the high-order byte in my of_t, and so forth.
  1304.  */
  1305. static void
  1306. mybytemap(map)
  1307. int map[];            /* -> int[SOF] */
  1308. {
  1309.     union {
  1310.         of_t o;
  1311.         char c[SOF];
  1312.     } u;
  1313.     register int *mp = &map[SOF];
  1314.     register int ntodo;
  1315.     register int i;
  1316.  
  1317.     u.o = 1;
  1318.     for (ntodo = (int)SOF; ntodo > 0; ntodo--) {
  1319.         for (i = 0; i < SOF; i++)
  1320.             if (u.c[i] != 0)
  1321.                 break;
  1322.         if (i == SOF) {
  1323.             /* trouble -- set it to *something* consistent */
  1324.             dprint(5, (debugfile, "mybytemap: nonexistent byte %d!!!\n", ntodo));
  1325.             for (i = 0; i < SOF; i++)
  1326.                 map[i] = i;
  1327.             return;
  1328.         }
  1329.         dprint(5, (debugfile, "mybytemap: byte %d\n", i));
  1330.         *--mp = i;
  1331.         while (u.c[i] != 0)
  1332.             u.o <<= 1;
  1333.     }
  1334. }
  1335.  
  1336. /*
  1337.  - bytemap - transform an of_t from byte ordering map1 to map2
  1338.  */
  1339. static of_t            /* transformed result */
  1340. bytemap(ino, map1, map2)
  1341. of_t ino;
  1342. int *map1;
  1343. int *map2;
  1344. {
  1345.     union oc {
  1346.         of_t o;
  1347.         char c[SOF];
  1348.     };
  1349.     union oc in;
  1350.     union oc out;
  1351.     register int i;
  1352.  
  1353.     in.o = ino;
  1354.     for (i = 0; i < SOF; i++)
  1355.         out.c[map2[i]] = in.c[map1[i]];
  1356.     return(out.o);
  1357. }
  1358.  
  1359. /*
  1360.  * This is a simplified version of the pathalias hashing function.
  1361.  * Thanks to Steve Belovin and Peter Honeyman
  1362.  *
  1363.  * hash a string into a long int.  31 bit crc (from andrew appel).
  1364.  * the crc table is computed at run time by crcinit() -- we could
  1365.  * precompute, but it takes 1 clock tick on a 750.
  1366.  *
  1367.  * This fast table calculation works only if POLY is a prime polynomial
  1368.  * in the field of integers modulo 2.  Since the coefficients of a
  1369.  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
  1370.  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
  1371.  * 31 down to 25 are zero.  Happily, we have candidates, from
  1372.  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
  1373.  *    x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
  1374.  *    x^31 + x^3 + x^0
  1375.  *
  1376.  * We reverse the bits to get:
  1377.  *    111101010000000000000000000000001 but drop the last 1
  1378.  *         f   5   0   0   0   0   0   0
  1379.  *    010010000000000000000000000000001 ditto, for 31-bit crc
  1380.  *       4   8   0   0   0   0   0   0
  1381.  */
  1382.  
  1383. #define POLY 0x48000000L    /* 31-bit polynomial (avoids sign problems) */
  1384.  
  1385. static long CrcTable[128];
  1386.  
  1387. /*
  1388.  - crcinit - initialize tables for hash function
  1389.  */
  1390. static void
  1391. crcinit()
  1392. {
  1393.     register int i, j;
  1394.     register long sum;
  1395.  
  1396.     for (i = 0; i < 128; ++i) {
  1397.         sum = 0L;
  1398.         for (j = 7 - 1; j >= 0; --j)
  1399.             if (i & (1 << j))
  1400.                 sum ^= POLY >> j;
  1401.         CrcTable[i] = sum;
  1402.     }
  1403.     dprint(5, (debugfile, "crcinit: done\n"));
  1404. }
  1405.  
  1406. /*
  1407.  - hash - Honeyman's nice hashing function
  1408.  */
  1409. static long
  1410. hash(name, size)
  1411. register char *name;
  1412. register int size;
  1413. {
  1414.     register long sum = 0L;
  1415.  
  1416.     while (size--) {
  1417.         sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
  1418.     }
  1419.     dprint(5, (debugfile, "hash: returns (%ld)\n", sum));
  1420.     return(sum);
  1421. }
  1422.  
  1423. /*
  1424.  - dbzdebug - control dbz debugging at run time
  1425.  */
  1426. int                /* old value */
  1427. dbzdebug(value)
  1428. int value;
  1429. {
  1430. #ifdef DBZDEBUG
  1431.     register int old = debug;
  1432.  
  1433.     debug = value;
  1434.     return(old);
  1435. #else
  1436.     return(-1);
  1437. #endif
  1438. }
  1439.